package Top_Interview_Questions.Tree;

import Top_Interview_Questions.Tree.Supple.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 吕庆龙
 * @Date: 2020/2/7 13:22
 * <p>
 * 功能描述:
 */
public class _0102 {


    /**
     *  3
     * / \
     * 9  20
     * /  \
     * 15   7
     */
    public static void main(String[] args) {
        _0102 test = new _0102();

        TreeNode root = new TreeNode(3);
        TreeNode node1 = new TreeNode(9);
        TreeNode node2 = new TreeNode(20);
        TreeNode node3 = new TreeNode(15);
        TreeNode node4 = new TreeNode(7);
        TreeNode node5 = new TreeNode(6);

        root.left = node1;
        root.right = node2;
        node2.left = node3;
        node2.right = node4;
        node1.left = node5;

        List<List<Integer>> lists = test.levelOrder1(root);
        System.out.println(lists);


    }

    /*--------------------------------------官方题解的递归--------------------------------------*/

    List<List<Integer>> levels = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder2(TreeNode root) {
        if (root == null) return levels;
        helper(root, 0);
        return levels;
    }

    public void helper(TreeNode node, int level) {
        // start the current level
        if (levels.size() == level)
            levels.add(new ArrayList<Integer>());

        // fulfil the current level
        levels.get(level).add(node.val);

        // process child nodes for the next level
        if (node.left != null)
            helper(node.left, level + 1);
        if (node.right != null)
            helper(node.right, level + 1);
    }

    /*----------------------------------------------------------------------------------------*/

    /*---------------------------------------我的递归------------------------------------------*/

    List<List<Integer>> lists = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder1(TreeNode root) {
        if (root == null) {
            return lists;
        }
        List<Integer> list = new ArrayList<>();
        recurtraver(root, 0, list);

        return lists;
    }


    public void recurtraver(TreeNode node, int level, List<Integer> list) {
        // start the current level
        if (lists.size() == level)
            lists.add(list);

        // fulfil the current level,这个地方很巧妙
        lists.get(level).add(node.val);

        // process child nodes for the next level
        if (node.left != null)
            recurtraver(node.left, level + 1, new ArrayList<>());
        if (node.right != null)
            recurtraver(node.right, level + 1, new ArrayList<>());
    }

    /*----------------------------------------------------------------------------------------*/
}
